package linkedList.分离合并;

import linkedList.BaseLinkedListTest;
import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 分隔链表86.java
 * @Description  https://leetcode-cn.com/problems/partition-list/
 * @createTime 2021年03月10日 18:26:00
 */
public class 分隔链表86 extends BaseLinkedListTest {
    /**
     * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     * <p>
     * 你应当 保留 两个分区中每个节点的初始相对位置。
     */
    public static ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode small = new ListNode(), big = new ListNode(), smallTmp = small, bigTmp = big;
        while (head != null) {
            if (head.val < x) {
                smallTmp.next=head;
                smallTmp=smallTmp.next;
            }else {
                bigTmp.next=head;
                bigTmp=bigTmp.next;
            }
            head = head.next;
        }
        bigTmp.next=null;
        smallTmp.next = big.next;
        return small.next;
    }

    public static void main(String[] args) {
        partition(createLinkedList(1, 4, 3, 2, 5, 2), 3);
    }
}
